/*
题目：警告一小时内使用相同员工卡大于等于三次的人
力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。

https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/
 */
public class AlertNames {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        HashMap<String, List<Integer>> cardMap = new HashMap<>();
        int n  = keyName.length;

        // 添加所有时间
        for (int i = 0; i < n; i ++) {
            List<Integer> take = cardMap.get(keyName[i]);
            if (take == null) { // 如果没有这个结果
                take = new ArrayList<>();
                take.add(parseTime(keyTime[i]));
                cardMap.put(keyName[i], take);
            } else {
                take.add(parseTime(keyTime[i]));
            }
        }

        List<String> src = new ArrayList<>();
        for (Map.Entry<String, List<Integer>> entry : cardMap.entrySet()) {
            String key = entry.getKey();
            List<Integer> value = entry.getValue();

            if (value.size() < 3) {
                continue;
            }

            // 如果长度大于 等于 3, 按照时间排序
            value.sort((Integer x, Integer y) -> {
                return x - y;
            });

            // 统计是否存在一小时 3 次
            if (check(value)) {
                src.add(key);
            }
        }

        src.sort((String x, String y) -> {return x.compareTo(y);}); // 引用类型的比较
        return src;
    }

    private boolean check(List<Integer> list) {
        // 维护一个大小为 3 的窗口
        int left = 0;
        Integer head = list.get(left);
        for (int i = 1; i < list.size(); i ++) {
            Integer cur = list.get(i);

            while (cur - head > 60) {
                head = list.get(++ left);
            }

            if (i - left + 1 == 3) {
                return true;
            }
        }

        return false;
    }


    private int parseTime(String s) {
        return Integer.parseInt(s.substring(0, 2)) * 60 + Integer.parseInt(s.substring(3));
    } 
}
